package Dijkstra旅途美女搭讪.测试;

import java.util.Arrays;
import java.util.Scanner;

//不会做，图算法
public class Main2 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			// 输入第一行数据
			int n = scanner.nextInt();
			int m = scanner.nextInt();

			// 定义迭代数据容器
			/**
			 * dij是目标的状态：最后问的结果
			 * 
			 * station是：站的权重，美女数
			 * 
			 * vis是二值数组：表示是否访问
			 * 
			 * road[][]数组的小标记录：车站之间有路的状态
			 */
			int[] dij = new int[n + 1], station = new int[n + 1], vis = new int[n + 1];
			int[][] road = new int[n + 1][n + 1];

			// 输入第二行数据
			for (int i = 1; i <= n; i++) {
				station[i] = scanner.nextInt();
			}

			// 输入第三行数据
			for (int i = 0; i < m; i++) {
				int p = scanner.nextInt();
				int q = scanner.nextInt();
				road[p][q] = 1;
				road[q][p] = 1;
			}

			// 初始化数据dij
			for (int i = 0; i <= n; i++) {
				dij[i] = Integer.MAX_VALUE;
			}

			// 观察二维数组的初始化状态
			Tools tools = new Tools();
			tools.print2DArray(road);

			// 状态迭代前的初始化
			dij[1] = station[1];
			vis[1] = 1;
			int tmp_i = 1;

			// 状态的改变只在vis和dij里面发生
			for (int i = 0; i < n - 1; i++) {

				for (int j = 1; j <= n; j++) {
					// 没有被访问过&&有路可走，公交站有直达车
					if (vis[j] == 0 && road[tmp_i][j] == 1) {
						// dij唯一变化的地方,上次状态和本次更新状态的较大值
						dij[j] = Math.min(dij[j], dij[tmp_i] + station[j]);
					}
				}

				// 修正tmp_min
				// 修正tmp_i
				int tmp_min = Integer.MAX_VALUE;
				for (int j = 1; j <= n; j++) {
					if (vis[j] == 0 && dij[j] <= tmp_min) {
						tmp_i = j;
						tmp_min = dij[j];
					}
				}

				// vis是一个01数据数组表示是不是查看过了，vis唯一变化的地方
				vis[tmp_i] = 1;
			}

			// 输出
			System.out.println(Arrays.toString(dij));
			System.out.println(Arrays.toString(station));
			System.out.println(Arrays.toString(vis));
			System.out.println();

			// 最终的输出
			System.out.println(dij[n]);
		}
		scanner.close();
	}

}